package dynamicStudy;

import java.util.Arrays;

public class MaxProfit4 {

    /**
     * LeetCode T188 买卖股票的最佳时机
     *
     * 给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
     *
     * 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
     *
     * 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * @param args
     */
    public static void main(String[] args) {

    }

    public int maxProfit(int k, int[] prices) {
        int days = prices.length;
        if (days < 2){
            return 0;
        }
        //如果交易次数大于天数，只要找到所有大于0的交易即可
        if (k >= days){
            return maxProfitUnlimited(prices);
        }
        //确定状态
        int[] buy = new int[k + 1];
        int[] sell = new int[k + 1];
        Arrays.fill(buy, Integer.MIN_VALUE);
        //记录交易次数
        for (int i = 0; i < days; i++){
            for (int j = 1; j <= k; j++){
                //第j次买入时的最大收益
                buy[j] = Math.max(buy[j], sell[j - 1] - prices[i]);
                sell[j] = Math.max(sell[j], buy[j] + prices[i]);
            }
        }
        return Arrays.stream(sell).max().getAsInt();
    }

    public int maxProfitUnlimited(int[] prices){
        int maxProfit = 0;
        for (int i = 1; i < prices.length; i++){
            if (prices[i] > prices[i - 1]){
                maxProfit += (prices[i] - prices[i - 1]);
            }
        }
        return maxProfit;
    }

    //三维数组解决问题
    public int maxProfit2(int k, int[] prices) {
        if (prices.length == 0){
            return 0;
        }
        //总天数
        int days = prices.length;
        k = Math.min(k, days/2);
        //有可能交易次数的二倍大于等于总天数，导致无法完成所有的交易次数
        int[][] buy = new int[days][k + 1];
        int[][] sell = new int[days][k + 1];

        //进行状态初始化
        buy[0][0] = -prices[0];
        sell[0][0] = 0;
        //定义非法状态
        for (int i = 1; i <= k; i++){
            buy[0][i] = sell[0][i] = Integer.MIN_VALUE/2;
        }
        //状态转移
        for (int i = 1; i < days; i++){
            //保持或者买入，初始化第一列
            buy[i][0] = Math.max(buy[i - 1][0], sell[i - 1][0] - prices[i]);
            for (int j = 1; j <= k; j++){
                buy[i][j] = Math.max(buy[i - 1][j], sell[i - 1][j] - prices[i]);
                sell[i][j] = Math.max(sell[i - 1][j], buy[i - 1][j - 1] + prices[i]);
            }
        }

        return Arrays.stream(sell[days - 1]).max().getAsInt();

    }
    //三维数组解决问题
    public int maxProfit3(int k, int[] prices) {
        if (prices.length == 0){
            return 0;
        }
        //总天数
        int days = prices.length;
        k = Math.min(k, days/2);
        //有可能交易次数的二倍大于等于总天数，导致无法完成所有的交易次数
        int[][] buy = new int[days][k + 1];
        int[][] sell = new int[days][k + 1];

        //进行状态初始化

//        sell[0][0] = 0;
        //定义非法状态
        for (int i = 1; i <= k; i++){
            buy[0][i] = Integer.MIN_VALUE;
        }
        buy[0][1] = -prices[0];
        //状态转移
        for (int i = 1; i < days; i++){
            for (int j = 1; j <= k; j++){
                buy[i][j] = Math.max(buy[i - 1][j], sell[i - 1][j - 1] - prices[i]);
                sell[i][j] = Math.max(sell[i - 1][j], buy[i - 1][j] + prices[i]);
            }
        }

        return Arrays.stream(sell[days - 1]).max().getAsInt();

    }
}
